1. Field of the Invention
This disclosure generally relates to techniques for providing robust load balancing in a distributed system. More specifically, this disclosure relates to techniques for detecting and preventing oscillatory load behavior in a multi-node distributed system.
2. Related Art
The proliferation of the Internet and large data sets have made data centers and clusters of computers increasingly common. For instance, “server farms” typically combine large numbers of computers that are connected by high-speed networks to support services that exceed the capabilities of an individual computer. A designated “load manager” typically receives incoming service requests for the cluster, and then distributes the requests across individual nodes using techniques that strive to maximize the throughput of the cluster.
Unfortunately, efforts to evenly distribute requests across a cluster can often lead to oscillatory behavior. For instance, if one cluster node becomes overloaded, a load manager may move work from the overloaded node to another node. However, as a result, the original node may run out of work and become idle, while the target node in turn becomes overloaded by the additional transferred work. Hence, re-balancing attempts may result in nodes oscillating between idle and overloaded states, leading to inefficient operation and degraded performance. System administrators sometimes attempt to use heuristic techniques to reduce oscillation, but such heuristics often do not generalize well, and thus typically fail under changing operational conditions.
Hence, what is needed are techniques for distributing requests across a multi-node distributed system without the above-described problems of existing techniques.